package indigo.collections
{
	import flash.events.Event;
	
	import indigo.utils.IDisposable;
	
	use namespace indigo;
	
	/**
	 * @author Sebastiaan Holtrop
	 * @example
	 * <code>
	 * <listing>
	 * <pre>
	 * // Create the LinkedList
	 * var myLinkedList:LinkedList = new LinkedList();
	 * 
	 * // Append an item at the end of the LinkedList. You can put any kind of primitive or object in a LinkedList
	 * myLinkedList.append(1);
	 * myLinkedList.append(2);
	 * 
	 * // Prepend an item at the beginning of the LinkedList
	 * myLinkedList.prepend(0);
	 * 
	 * // Add an item after the given item. In this case, it wil add 4 after 2.
	 * myLinkedList.addAfter(2, 4);
	 * // And add 3 after 4
	 * myLinkedList.addBefore(4, 3);
	 * 
	 * // You can get the number of items in a LinkedList by calling the size property.
	 * trace("size", myLinkedList.size);
	 * 
	 * // Use the iterator to loop over the LinkedList
	 * var myIterator:IIterator = myLinkedList.iterator();
	 * 
	 * while (myIterator.hasNext())
	 * {
	 * 	// Be sure to call the next method in loops like this, to avoid endless loops
	 * 	var myItem:* = myIterator.next();
	 * }
	 * 
	 * // You can also get the items in a LinkedList as an Array.
	 * var myArray:Array = myLinkedList.toArray();
	 * 
	 * // Use the shift method to remove the first element in the list
	 * myLinkedList.shift();
	 * 
	 * // Use the pop method to remove the last element in the list
	 * myLinkedList.pop();
	 * </pre>
	 * </listing>
	 * </code> 
	 */	
	public class LinkedList implements IDisposable, ICollection
	{
		
		internal var firstLinkedListItem:LinkedListItem;
		internal var lastLinkedListItem:LinkedListItem;
		
		/**
		 * Appends an item at the end of the LinkedList 
		 * @param item
		 */		
		public function append(item:*):void
		{
			var myLinkedListItem:LinkedListItem = new LinkedListItem( item );
			
			if (lastLinkedListItem)
			{
				lastLinkedListItem.next = myLinkedListItem;
				myLinkedListItem.previous = lastLinkedListItem;
				lastLinkedListItem = myLinkedListItem;
			}
			else
			{
				firstLinkedListItem = myLinkedListItem;
				lastLinkedListItem = myLinkedListItem;
			}
		}
		
		
		/**
		 * Prepends an item at the beginning of the LinkedList 
		 * @param item
		 */
		public function prepend(item:*):void
		{
			if (firstLinkedListItem)
			{
				var myLinkedListItem:LinkedListItem = new LinkedListItem( item );
				firstLinkedListItem.previous = myLinkedListItem;
				myLinkedListItem.next = firstLinkedListItem;
				firstLinkedListItem = myLinkedListItem;
			}
			else
			{
				append(item);
			}
		}
		
		
		/**
		 * Adds an item before the given item in the LinkedList. 
		 * @param beforeItem The item before which the item must be added
		 * @param item the item to add to the LinkedList
		 * @return Boolean Returns true if the given beforeItem exists in the list and the 
		 * given item can be added before this item. Otherwise returns false.
		 */		
		public function addBefore(beforeItem:*, item:*):Boolean
		{
			var myBeforeLinkedListItem:LinkedListItem = getLinkedListItemByItem(beforeItem);
			
			// There's no LinkedListItem with the given item in the collection
			if (!myBeforeLinkedListItem)
			{
				return false;
			}
			
			// Is it the last item in the collection?
			if (myBeforeLinkedListItem == firstLinkedListItem)
			{
				// Then append it at the end, so we atomatically keep track of the lastLinkedListItem
				prepend(item);
				return true;
			}
			
			var myNewLinkedListItem:LinkedListItem = new LinkedListItem( item );
			
			myNewLinkedListItem.next = myBeforeLinkedListItem;
			myNewLinkedListItem.previous = myBeforeLinkedListItem.previous;
			
			myBeforeLinkedListItem.previous.next = myNewLinkedListItem;
			myBeforeLinkedListItem.previous = myNewLinkedListItem;
			
			return true;
		}
		
		
		/**
		 * Adds an item after the given item in the LinkedList. 
		 * @param afterItem The item after which the item must be added
		 * @param item the item to add to the LinkedList
		 * @return Boolean Returns true if the given afterItem exists in the list and the 
		 * given item can be added after this item. Otherwise returns false.
		 */	
		public function addAfter(afterItem:*, item:*):Boolean
		{
			var myAfterLinkedListItem:LinkedListItem = getLinkedListItemByItem(afterItem);
			
			// There's no LinkedListItem with the given item in the collection
			if (!myAfterLinkedListItem)
			{
				return false;
			}
			
			// Is it the last item in the collection?
			if (myAfterLinkedListItem == lastLinkedListItem)
			{
				// Then append it at the end, so we atomatically keep track of the lastLinkedListItem
				append(item);
				return true;
			}
			
			var myNewLinkedListItem:LinkedListItem = new LinkedListItem( item );
			
			myNewLinkedListItem.next = myAfterLinkedListItem.next;
			myNewLinkedListItem.previous = myAfterLinkedListItem;
			
			myAfterLinkedListItem.next.previous = myNewLinkedListItem;
			myAfterLinkedListItem.next = myNewLinkedListItem;
			
			return true;
		}
		
		
		
		public function removeItem(item:*):Boolean
		{
			var myLinkedListItem:LinkedListItem = getLinkedListItemByItem(item);
			if (myLinkedListItem)
			{
				if (myLinkedListItem == firstLinkedListItem)
				{
					shift();
					return true;
				}
				if (myLinkedListItem == lastLinkedListItem)
				{
					pop();
					return true;
				}
				
				myLinkedListItem.previous.next = myLinkedListItem.next;
				myLinkedListItem.next.previous = myLinkedListItem.previous;
				myLinkedListItem.dispose();
			}
			return false;
		}
		
		/**
		 * Function to retrieve the number of items in the LinkedList 
		 * @return int The number of items in LinkedList
		 * 
		 */		
		public function get size():int
		{
			var myIterator:IIterator = iterator();
			
			var myCount:int = 0;
			
			// Loop the collection
			while (myIterator.hasNext())
			{
				myIterator.next();
				myCount++;
			}
			
			return myCount;
		}
		
		
		public function toArray():Array
		{
			var myIterator:IIterator = iterator();
			
			var myResultArray:Array = new Array();
			
			// Loop the collection
			while (myIterator.hasNext())
			{
				myResultArray.push(myIterator.next());
			}
			
			return myResultArray;
		}
		
		
		/**
		 * Returns a string representation of the elements in the LinkedList.
		 * @return String
		 */		
		public function toString():String
		{
			var myReturnValue:String = "";
			var myIterator:IIterator = iterator();
			
			// Loop the collection
			while (myIterator.hasNext())
			{
				myReturnValue += myIterator.next();
				if (myReturnValue.length > 0 && myIterator.hasNext())
				{
					myReturnValue +=",";
				}
			}
			return myReturnValue;
		}
		
		
		/**
		 * Creates a new IIterator, needed for looping over the collection.
		 * @param type The type of Iterator
		 * @return IIterator
		 */		
		public function iterator(type:String = null):IIterator
		{
			return new LinkedListIterator(this);
		}
		
		
		/**
		 * Removes the first element from the collection and returns that element.
		 * @return *
		 */		
		public function shift():*
		{
			if (firstLinkedListItem)
			{
				var myReturnObject:* = firstLinkedListItem.data;
				if (firstLinkedListItem.next)
				{
					// Save a reference, so we can dispose it later
					var myLinkedListItemForDisposal:LinkedListItem = firstLinkedListItem;
					
					firstLinkedListItem = firstLinkedListItem.next;
					firstLinkedListItem.previous = null;
					
					// Dispose it
					myLinkedListItemForDisposal.dispose();
					
					return myReturnObject;
				}
				
				if (firstLinkedListItem)
				{
					firstLinkedListItem.dispose();
					firstLinkedListItem = null;
				}
				if (lastLinkedListItem)
				{
					lastLinkedListItem.dispose();
					lastLinkedListItem = null;
				}
				
				return myReturnObject;
			}
			return null;
		}
		
		
		/**
		 * Removes the last element from the collection and returns the value of that element. 
		 * @return * 
		 */		
		public function pop():*
		{
			if (lastLinkedListItem)
			{
				var myReturnObject:* = lastLinkedListItem.data;
				
				if (lastLinkedListItem.previous)
				{
					// Save a reference, so we can dispose it later
					var myLinkedListItemForDisposal:LinkedListItem = lastLinkedListItem;
					
					lastLinkedListItem = lastLinkedListItem.previous;
					lastLinkedListItem.next = null;
					
					// Dispose it
					myLinkedListItemForDisposal.dispose();
					
					return myReturnObject;
				}
				
				if (firstLinkedListItem)
				{
					firstLinkedListItem.dispose();
					firstLinkedListItem = null;
				}
				if (lastLinkedListItem)
				{
					lastLinkedListItem.dispose();
					lastLinkedListItem = null;
				}
				
				return myReturnObject;
			}
			return null;
		}
		
		
		public function isEmpty():Boolean
		{
			if (!firstLinkedListItem && !lastLinkedListItem)
			{
				return true;
			}
			return false;
		}
		
		/**
		 * Disposes this collection and it's elements 
		 * @param event
		 * 
		 */		
		public function dispose( event:Event = null ):void
		{
			while (!isEmpty())
			{
				pop();
			}
		}
		
		
		private function getLinkedListItemByItem(item:*):LinkedListItem
		{
			var myIterator:LinkedListIterator = iterator() as LinkedListIterator;
			
			// Loop the collection
			while (myIterator.hasNext())
			{
				// Get the current LinkedListItem
				var myCurrentLinkedListItem:LinkedListItem = myIterator.nextLinkedListItem();
				
				// Check if the data property matches the given item
				if (myCurrentLinkedListItem.data == item)
				{
					return myCurrentLinkedListItem;
				}
			}
			
			return null;
		}
	}
}